// Written by Craig'n'Dave
using System;
using System.Collections.Generic;
// Merge sort using recursion method 2
// This version of a merge sort pops items out of the sub-list when merging until none are left
namespace ConsoleApp1
{
    class Program
    {
        static List<string> merge_sort(List<string> items)
        {
            // Split step
            if (items.Count == 1)
            {
                return items;
            }
            else
            {
                int mid = items.Count / 2;
                // list1 contains the first half of the items
                List<string> list1 = new List<string>();
                for (int index = 0; index < mid; index++)
                {
                    list1.Add (items[index]);
                }
                // list2 contains the second half of the items
                List<string> list2 = new List<string>();
                for (int index = mid; index < items.Count; index++)
                {
                    list2.Add (items[index]);
                }

                list1 = merge_sort(list1);
                list2 = merge_sort(list2);
                // Merge step
                return merge(list1, list2);
            }
        }

        static List<string> merge(List<string> list1, List<string> list2)
        {
            List<string> new_list = new List<string>();
            while ((list1.Count > 0) && (list2.Count > 0))
            {
                // Check each item in each list, and add the smallest item to a new list
                if (string.Compare(list1[0], list2[0]) < 0)
                {
                    new_list.Add(list1[0]);
                    list1.RemoveAt(0);
                }
                else
                {
                    new_list.Add(list2[0]);
                    list2.RemoveAt(0);
                }
            }

            // Add left over items from the remaining list
            while (list1.Count > 0)
            {
                new_list.Add(list1[0]);
                list1.RemoveAt(0);
            }

            while (list2.Count > 0)
            {
                new_list.Add(list2[0]);
                list2.RemoveAt(0);
            }
            return new_list;
        }

        // Main program starts here
        static void Main(string[] args)
        {
            List<string> items = new List<string> { "Florida", "Georgia", "Delaware", "Alabama", "California" };
            items = merge_sort(items);
            Console.WriteLine(String.Join(", ", items));
        }
    }
}
